package com.whros.algorithm.sort;

import java.util.Comparator;

/**
 *
 * 堆排序算法
 * @author whroid
 * @date 18/10/20 下午4:24
 *
 * 算法简介
 *
 * 利用平衡二叉树的特性，快速找到非叶子节点，对所有非叶子节点比较，将最大最小值调整到根节点上。再利用递归操作找出所有的剩余队列中最大最小值
 *
 * 时间复杂度为 O(n log n) 如何计算时间复杂度？
 *
 *操作步骤：
 * 1，将数据【Arr（N）】按照列表数组顺序，一次放入平衡二叉树中
 * 2，通过一次堆的全量调整获取最大或者最小值
 * 3，将筛选出的值和最后一个交换，在Arr[n-1]数组重复对操作，直至排序完成
 *
 * 一次堆操作：
 *     1，从最后一个非叶子节点开始（坐标为n/2  - 1)
 *     2,依次和左右子节点比较获取最大（最小）值并替换
 *     3，依非叶子节点顺序执行第2步，直到最后一个非叶子节点（根节点坐标为0）
 *     4，根节点即为最大（最小）值
 *
 */
public class HeapSortAlgorithm<T extends Comparable> implements SortAlgorithm<T> {

    @Override
    public void sortByDesc(T[] arr) {
        sort(arr, (a, b) -> b.compareTo(a));
    }

    @Override
    public void sortByAsc(T[] arr) {
        sort(arr, (a, b) -> a.compareTo(b));
    }


    @Override
    public void sort(T[] arr, Comparator<T> comparable) {
        int length = arr.length;
        for (int i = length; i > 0; i--) {
            buildHeap(arr, i, comparable);
            SortUtils.print(arr);
            SortUtils.swap(arr, 0, i - 1);
        }
    }

    /**
     *
     * @param arr
     * @param length
     * @param compare
     */
    private void buildHeap(T[] arr, int length, Comparator<T> compare) {

        for (int rootIndex = length / 2 - 1; rootIndex >= 0; rootIndex--) {

            int rightIndex = rootIndex * 2 + 2;
            int leftIndex = rootIndex * 2 + 1;

            int exchageIndex = rootIndex;

            if (rightIndex < length && compare.compare(arr[exchageIndex], arr[rightIndex]) < 0) {
                exchageIndex = rightIndex;
            }

            if (leftIndex < length && compare.compare(arr[exchageIndex], arr[leftIndex]) < 0) {
                exchageIndex = leftIndex;
            }

            if (exchageIndex != rootIndex) {
                SortUtils.swap(arr, rootIndex, exchageIndex);
            }
        }
    }

}
